package com.leetcode.LC;


import java.util.*;
import java.lang.*;

public class LC506 {

    //另一种思路，用Map记录成绩和初始位置，然后对数组排序遍历，将名词填入合适的位置

    public String[] findRelativeRanks(int[] nums) {

        List<String> list = new ArrayList<>();
        int[] a = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            a[i]=nums[i];
        }
        Arrays.sort(a);

        for (int num : nums) {
            if ((nums.length - search(a, num)) == 1) {
                list.add("Gold Medal");
            } else if ((nums.length - search(a, num)) == 2) {
                list.add("Silver Medal");
            } else if ((nums.length - search(a, num)) == 3) {
                list.add("Bronze Medal");
            } else {
                list.add((nums.length - search(a, num)) + "");
            }
        }
        /*String[] rs = new String[list.size()];
        for (int i = 0; i < list.size(); i++) {
            rs[list.size()-i-1] = list.get(i);
        }*/
        return list.toArray(new String[list.size()]);
    }

    public int search(int[] nums, int target) {
        int a = 0, b = nums.length - 1;
        int mid = (a + b) / 2;
        while (a <= b) {
            if (nums[mid] == target) {
                return mid;
            }
            if (target > nums[mid]) {
                a = mid + 1;
            }
            if (target < nums[mid]) {
                b = mid - 1;
            }
            mid = (a + b) / 2;
        }
        return -1;
    }

    public String[] findRelativeRanks2(int[] nums) {
        //利用Map记录成绩和原始位置，Key为成绩，Value为位置
        Map<Integer, Integer> map=new HashMap<Integer, Integer>();
        for(int i=0; i<nums.length; i++){
            map.put(nums[i], i);
        }
        //按照成绩排序
        Arrays.sort(nums);
        //定义一个String类型的数组result来存放最终结果
        String[] result = new String[nums.length];

        int order=1;
        for(int i=nums.length-1; i>=0; --i){

            switch(order){
                case 1: result[map.get(nums[i])]="Gold Medal";
                    break;
                case 2: result[map.get(nums[i])]="Silver Medal";
                    break;
                case 3: result[map.get(nums[i])]="Bronze Medal";
                    break;
                default: result[map.get(nums[i])]=""+(nums.length-i);
                    break;
            }
            order++;
        }
        return result;
    }


    public static void main(String[] args) {
        for (String relativeRank : new LC506().findRelativeRanks(new int[]{5, 4, 3, 2, 1})) {
            System.out.print(relativeRank + ",");
        }
    }
}
